/*

struct ListNode {

    int val;

    struct ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}

};*/

ListNode* Listmid(ListNode* head)

{

    ListNode* fast = head;

    ListNode* slow = head;

    while (fast && fast->next)

    {

        slow = slow->next;

        fast = fast->next->next;

    }

    return slow;

}

ListNode* reverseList(ListNode* head)

{

    ListNode* n1 = NULL;

    ListNode* n2 = head;

    ListNode* n3 = head->next;

    while (n2)

    {

        n2->next = n1;

        n1 = n2;

        n2 = n3;

        if (n3 != NULL)

        {

            n3 = n3->next;

        }

    }

    return n1;

}

class PalindromeList {

public:

    bool chkPalindrome(ListNode* A) {

        ListNode* head = A;

        ListNode* pcur = A;

        ListNode* mid = Listmid(head);

        ListNode* newhead = reverseList(mid);

        while (newhead)

        {

            if (pcur->val != newhead->val)

            {

                return false;;

            }

            pcur = pcur->next;

            newhead = newhead->next;

        }

        return true;

    }

};
